Solution: Regions Cut by Slashes
Let's solve the Regions Cut By Slashes problem using the Union Find pattern.
We'll cover the following
Statement#
An grid is composed of , squares, where each square consists of a “/”, “\”, or a blank space. These characters divide the square into adjacent regions.
Given the grid represented as a string array, return the number of regions.
Note:
- Backslash characters are escaped, so “\” is represented as “\\”.
- A square in the grid will be referred to as a box.
Constraints:
- The grid consists of only “/”, “\”, or " " characters.
- 1
grid.length30
The following demonstration shows how the grid can be visualized:
1 of 16
2 of 16
3 of 16
4 of 16
5 of 16
6 of 16
7 of 16
8 of 16
9 of 16
10 of 16
11 of 16
12 of 16
13 of 16
14 of 16
15 of 16
16 of 16
Solution#
The idea is to divide each box in the grid into four regions representing its north, west, east, and south regions. At the start, an grid will contain regions. We will gradually reduce the number of regions by merging the regions inside each box based on the character they contain and then connecting them with their neighboring boxes. This merging and connecting will be done using the union find algorithm. In the union find algorithm, the union by rank and path compression optimizations will be applied. In the end, the number of connected components will represent the correct number of regions inside the grid.
Here’s how the algorithm works:
-
We create a
parentarray containing elements where each element equals its corresponding index.-
Every four consecutive elements in this array represent a box in the grid.
-
We associate each grid square with four nodes—north, west, east, and south—representing four triangles inside the square. That’s how every one of these four elements inside the parent list represents the north, west, east, and south components of the box, respectively.
-
Each element in the array is initially equal to its respective index. For example:
-
The
grid[0][0]box will comprise of the elements:0,1,2, and3. -
The
grid[0][1]box will comprise of the elements:4,5,6, and7, and so on.
-
-
-
Next, we traverse each character of the
gridarray: -
We use the
unionmethod to merge the regions within each box depending on the character it contains:-
If the box contains a “/” character, it will be partitioned into two regions. Therefore, we will merge the north-west and east-south regions to convert the box into two connected components.
-
If the box contains a “\\” character, it will be partitioned into two regions. Therefore, we will merge the north-east and west-south regions to convert the box into two connected components.
-
If the box contains a " " character, it will be converted to a single region. Therefore, we combine all four regions of the box to convert the box into a single connected component.
-
The illustration below shows how the regions within a box are merged:
1 of 3
2 of 3
3 of 3
-
Next, we connect the current box with the neighboring boxes on it’s top, bottom, left, and right:
-
The north region of the current box connects with the south region of the box above it.
-
The south region of the current box connects with the north region of the box below it.
-
The west region of the current box connects with the east region of the box to its left.
-
The east region of the current box connects with the west region of the box to its right.
-
-
After the
gridarray has been traversed completely, the number of connected components inparentarray are equal to the correct number of regions in the grid. So, we will traverse theparentarray to find the number of connected components:-
We maintain a variable,
count, initialized to 0 to count the number of connected components. -
For each element,
parents[i], we will use thefind(parents[i])method to check if the current node is a parent of itself, i.e. the current elementparents[i]is equal to its respective index,i:-
If it is, we have found a connected component and increment the
countvariable. -
Otherwise, we move forward.
-
-
-
After the
parentarray has been traversed completely, we returncountas it contains the number of regions in the grid.
The slides below illustrate how the algorithm runs:
1 of 40
2 of 40
3 of 40
4 of 40
5 of 40
6 of 40
7 of 40
8 of 40
9 of 40
10 of 40
11 of 40
12 of 40
13 of 40
14 of 40
15 of 40
16 of 40
17 of 40
18 of 40
19 of 40
20 of 40
21 of 40
22 of 40
23 of 40
24 of 40
25 of 40
26 of 40
27 of 40
28 of 40
29 of 40
30 of 40
31 of 40
32 of 40
33 of 40
34 of 40
35 of 40
36 of 40
37 of 40
38 of 40
39 of 40
40 of 40
Let’s take a look at the code for this solution below:
Time complexity#
The time complexity of this solution is , (where is the length of the grid) and can be calculated as:
-
The nested loops iterate over each character in the grid, resulting in iterations.
-
The time complexity of the the
unionandfindfunctions is as both path compression and union find by rank are being used. is almost constant time and grows very slowly with the input size, so the time complexity of both these functions can be considered as constant time for practical purposes. -
The loop to find the number of connected components traverses the parent array once, resulting in iterations.
Therefore, the overall time complexity becomes , which simplifies to .
Space Complexity#
The space complexity of this solution is and can be calculated as:
-
Space occupied by the
parentarray: . -
Space occupied by the
rankarray: .
Therefore, the overall time complexity is , which simplifies to .
Regions Cut by Slashes
Accounts Merge